// https://www.lintcode.com/problem/prettyprint/

public class Solution {
    /**
     * @param text: the text to print
     * @param width: the width of the window
     * @return: return the result of pretty print.
     */
    public List<String> prettyPrint(List<List<String>> text, int width) {
        // write your code here
        List<String> ret = new ArrayList<>();
        ret.add(buildCharLine('*', width + 2));
        for (List<String> line : text) {
            List<String> _line = new ArrayList<>();
            int n = width;
            for (String word : line) {
                if (n >= (word.length() + 1)) {
                    _line.add(word);
                    n -= (word.length() + 1);
                } else {
                    if (n == word.length()) {
                        _line.add(word);
                        addLine(ret, _line, width);
                        _line.clear();
                        n = width;
                    } else {
                        addLine(ret, _line, width);
                        _line.clear();
                        _line.add(word);
                        n = width - (word.length() + 1);
                    }
                }
            }
            if (_line.size() > 0) {
                addLine(ret, _line, width);
            }
        }
        ret.add(buildCharLine('*', width + 2));
        return ret;
    }
    
    private String buildCharLine(char c, int width) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < width; ++i) {
            sb.append(c);
        }
        return sb.toString();
    }
    
    private void addLine(List<String> ret, List<String> line, int width) {
        String fmt = String.join(" ", line);
        ret.add("*" + fmt + buildCharLine(' ', width - fmt.length()) + "*");
    }
}